"""
背包问题
01背包
重量w[i]，价值 v[i]
背包容量c
记录最优价值m[i][j]:(从第i、i+1、...、n的最优价值，j为背包容量)
m是一个n x c的矩阵
            max{m[i+1][j],m[i+1][j-w[i]]+v[i]}, j >= w[i]
m[i][j] =
            m[i+1][j],              j < w[i]

            v[n],   j >= w[n]
m[n][j] =
            0,      j < w[n]
"""

import numpy as np


def KnapMutrix(w, v, m, c, n):
    # 初始化m[n][j]
    for j in range(0, c + 1):
        if j >= w[n]:
            m[n][j] = v[n]
        else:
            m[n][j] = 0
    i = n - 1
    while i >= 0:
        for j in range(c + 1):
            if j >= w[i] and m[i + 1][j] <= m[i + 1][j - w[i]] + v[i]:
                m[i][j] = m[i + 1][j - w[i]] + v[i]
            else:
                m[i][j] = m[i + 1][j]
        i = i - 1


w = [0, 5, 4, 3, 6]
v = [0, 5, 6, 8, 9]
m = np.zeros((5, 11), dtype=int)
KnapMutrix(w, v, m, 10, 4)
print(m)
